Packet-switched networks (e.g., the Internet) are useful for transmitting packetized data between different network devices. Such networks typically include nodes configured to communicate with each other by sending packets over links. Often, communications sent from one node must travel through intermediary nodes before reaching the destination node. The intermediary nodes are able to decipher routing information contained in the communication packets and forward (i.e., route) the packets in accordance with the information. The packets sent by a node may take different network paths to reach the destination node, where the packets are reassembled.
The routing of packets over packet-switched networks continues to become more complex, especially for networks that support time-sensitive applications (e.g., voice-over-IP) and/or provide quality-of-service (“QoS”) guarantees to customers. Such networks are able to support different levels of service by prioritizing some communication packets over others. Prioritization of packets for transmission is typically performed in the nodes (e.g., at the routers) of networks, where packets are queued for transmission over a link.
Priority queuing refers to techniques for queuing packets for transmission based on priority. Many priority queuing techniques separate packets into distinct priority queues based on priority. Such techniques typically decipher priority levels of incoming packets, usually from information contained in the packets, and add the packets to the priority queues, with the highest priority packets being added to the highest priority queues, and so on down through the lowest priority queue. The packets in the different queues are then selected for transmission based on priority, with any queues in the highest priority queue being selected first for transmission. The practice of transmitting higher priority packets ahead of lower priority packets can be referred to as delay priority.
While conventional priority queuing techniques have enabled many packet-switched networks to support different levels of service having various QoS requirements, the queuing techniques exhibit shortcomings under certain routine network conditions. For example, delay priority often causes low priority queues to become congested when high priority traffic continues to flow into the high priority queues and dominate allocation of available bandwidth. Low priority queues are likely to continue to be filled even when all available bandwidth is being used for high priority traffic. This causes long delays for low priority traffic waiting for higher priority queues to clear.
If the higher priority queues are eventually cleared of packets, the low priority packets in the low priority queues will be suddenly transmitted using all available resources. The buildup followed by sudden transmittal of low priority packets may repeat with unpredictable inconsistency per cycle. Each cycle may vary significantly from other cycles due to the unpredictable nature of high priority traffic demands. Consequently, low priority traffic often exhibits significant discrepancies in lengths of transmission delay (i.e., latency). Unfortunately, significant variations may adversely affect congestion control mechanisms commonly used by network transmission protocols (e.g., transmission control protocol [“TCP”]). In other words, conventional priority queuing techniques suffer from the tendency to create unfair and highly variable traffic flows for low priority traffic. This problem may be referred to as a lack of flow fairness.
To help avoid congestion in priority queues, several conventional queuing techniques have been introduced for dropping packets from the priority queues. Unfortunately, these techniques are rather limited because they are applied to each priority queue on an individual basis. The dropping of packets is performed at each particular priority queue without considering packets in the other priority queues. Consequently, low priority queues may continue to be filled with packets without dropping them even when the packets will not be transmitted for a lengthy amount of time because of the presence of significant high priority traffic that will take precedence over lower priority traffic within the available bandwidth. Conventional queuing techniques fail to consider the presence of higher priority packets in the higher priority queues when determining the appropriate drop rate for lower priority queues.
Thus, although conventional queuing techniques are able to control transmission delay based on priority, current packet-dropping techniques do not adequately alleviate congestion in low priority queues because the techniques drop packets from the priority queues without considering the status of other priority queues. Moreover, conventional queuing techniques related to priority queuing do not adequately support flow fairness for low priority traffic.